import java.util.Iterator;

public class HashTable implements MemoryManager
{
	private LinkedList[] buckets; // the actual buckets implemented with LinkedList chaining
	private int N; // the number of elements in the table
	private int M; // the number of buckets
	private int maxSize; // the starting size of the table
	private boolean canRehash; // if the number of buckets == inital memory size, this is false
	private int counter; // counter for the Memory IDs

	private Memory[] usedMemory;
	private SortingArray sortingArray;

	/**
	 * Creates a HashTable object initially with 4 buckets
	 * @param size the maximum size of Memory object possible
	 */
	public HashTable(int size)
	{
		this.buckets = new LinkedList[4];
		for (int i = 0; i < buckets.length; i++)
			buckets[i] = new LinkedList();

		this.N = 0;
		this.M = 4;
		this.maxSize = size;
		this.canRehash = true;

		Memory max = new Memory(maxSize, 0, -1);
		buckets[M - 1].insert(max);
		N++;

		usedMemory = new Memory[4];
		sortingArray = new SortingArray();
		sortingArray.insert(max);

		counter = 1;
	}

	/** Attempts to allocate memory of the specified size. Returns a String containing
	 *  the UID of the transaction and the starting address if successful. If unsuccessful, -1.
	 * @param size The amount of memory to allocate
	 * @return the ID and the address of the Memory as a String in the form "ID Address"
	 */
	public String allocate(int size)
	{               
		if (size > maxSize || size < 1) // definitely can't/shouldn't be allocated
		{
			Memory m = new Memory(size, -1, counter++);
			return "" + m.id() + " -1";
		}

		Memory greater = findFirstGreaterThan(size);
		if (greater == null) // couldn't find one big enough
		{
			Memory m = new Memory(size, -1, counter++);
			return "" + m.id() + " -1";
		}

		// create the new Memory
		Memory m = new Memory(size, greater.address(), counter++);

		// resize array if necessary, insert
		while (m.id() >= usedMemory.length)
		{
			Memory[] temp = new Memory[usedMemory.length * 2];
			for (int i = 0; i < usedMemory.length; i++)
				temp[i] = usedMemory[i];
			usedMemory = temp;
		}
		usedMemory[m.id()] = m;

		// change greater's size and starting address
		greater.setSize(greater.size() - size);
		greater.setAddress(greater.address() + size); // could cause problems. memory address over the start?
		sortingArray.remove(greater.address());

		if (greater.size() == 0)
			return "" + m.id() + " " + m.address();

		if (insert(greater))
		{
			sortingArray.insert(greater);
			return "" + m.id() + " " + m.address();
		}
		else
			return "ERROR";
	}

	/** Attempts to free the memory allocated at the Block with the designated UID. Returns a String stating whether
	 * the memory was successfully freed or not. 
	 * @param UID The unique ID number of the memory block
	 * @return "SUCCESS" if successful or "FAILED" otherwise
	 */
	public String deallocate(int id)
	{
		if (id >= usedMemory.length || id <= 0)
			return "FAILED";

		Memory m = usedMemory[id];
		if (m == null)
			return "FAILED";
		usedMemory[id] = null;

		sortingArray.insert(m);
		if (insert(m))
			return "SUCCESS";
		else
			return "FAILED";
	}

	/**
	 * Inserts a Memory object into the HashTable
	 * @param m the Memory object to insert
	 * @return true if successful, false otherwise
	 */
	private boolean insert(Memory m)
	{       
		if ((N + 1) * 0.75 >= M) // need to rehash
		{
			if (canRehash)
			{
				if (maxSize / M == 1) // 1 bucket per size
				{
					rehash(maxSize);
					canRehash = false;
				}
				else
					rehash(M * 2); // need to make it bigger
			}
		}

		int index = hash(m.size());

		buckets[index].insert(m);
		N++;            
		return true;
	}

	/**
	 * Finds the first element in the HashTable whose size is greater than the size argument. 
	 * It then removes that element from the table and returns it for use later
	 * from the table
	 * @param size the size to find data greater than
	 * @return the Memory found
	 */
	private Memory findFirstGreaterThan(int size)
	{
		int index = hash(size);
		Memory m = buckets[index].findFirstGreaterThan(size);

		while (m == null)
		{
			index++;
			if (index >= M)
				return null;
			m = buckets[index].findFirstGreaterThan(size);
		}
		buckets[index].delete(m);
		N--;
		return m;
	}

	/**
	 * The hash function for the HashTable that divides the size - 1 by the interval of each bucket
	 * @param size the size to hash
	 * @return the index which bucket it should go in
	 */
	private int hash(int size)
	{
		double denom = ((double) maxSize / M);
		return (int) ((size - 1) / denom);
	}

	/**
	 * Rehashes the data if the ratio of number of elements in the table to the number of buckets is about 0.75
	 * @param newSize the new number of buckets
	 */
	private void rehash(int newSize)
	{
		LinkedList[] newBuckets = new LinkedList[newSize];

		for (int i = 0; i < newSize; i++)
			newBuckets[i] = new LinkedList();

		Iterator<Memory> it = iterator();

		M = newSize;

		while (it.hasNext())
		{
			Memory data = it.next();

			if (data != null)
			{
				int index = hash(data.size());
				newBuckets[index].insert(data);
			}
		}

		buckets = newBuckets;
	}

	/**
	 * Generates a visual representation of the HashTable
	 * @return the representation
	 */
	public String toString()
	{
		String s = "";
		for (int i = 0; i < buckets.length; i++)
		{
			s += "[" + i + "] ";
			if (buckets[i] != null)
				s += buckets[i].toString();
			s += "\n";
		}

		s += "Used Memory: ";

		for (int i = 0; i < usedMemory.length; i++)
		{
			Memory m = usedMemory[i];
			if (m != null)
				s += m + " ";
		}
		s += "\n";
		s += "SortingArray: " + sortingArray.toString();
		return s;
	}

	/**
	 * Checks to see if the HashTable is empty
	 * @return true if empty, false otherwise
	 */
	public boolean isEmpty() 
	{
		return N == 0;
	}

	/**
	 * Gets the number of elements in the HashTable
	 * @return the size
	 */
	public int getSize() 
	{
		return N;
	}

	/**
	 * Deletes data from the HashTable
	 * @param size the size of Memory to be deleted
	 * @return true if successful, false otherwise
	 */
	public boolean delete(int size) 
	{
		if (remove(size) == null)
			return false;
		return true;
	}

	/**
	 * Removes data from the HashTable
	 * @param size the size of Memory to remove
	 * @return the Memory removed
	 */
	public Memory remove(int size)
	{
		if (size > maxSize || size < 0)
			return null;
		int index = hash(size);
		Memory m = buckets[index].delete(size);
		N--;
		return m;
	}

	/**
	 * Searches the table for a specific Memory object
	 * @param m the object to search for
	 * @return the object itself if found, null otherwise
	 */
	public Memory find(Memory m) 
	{
		return null;
	}

	/**
	 * Calls defrag on the SortingArray, clears the MemoryManager, then  rebuilds it again from the sorted SortingArray.
	 */
	public void defrag() 
	{
		sortingArray = sortingArray.defrag();
		emptyTable();
		counter--;

		for (Memory m : sortingArray)
		{
			if (m != null)
				insert(m);
		}
	}

	/**
	 * Resets the table by emptying it's contents and resetting its values
	 */
	public void emptyTable()
	{
		buckets = new LinkedList[4];
		for (int i = 0; i < buckets.length; i++)
			buckets[i] = new LinkedList();

		this.N = 0;
		this.M = 4;
		this.canRehash = true;          
	}

	/**
	 * This will call quicksort and bucketsort in that order!! And pass the Statistic as a parameter
	 * @param s the Statistic
	 * @throws InterruptedException 
	 */
	public void sort(Statistics s) throws InterruptedException
	{
		sortingArray.quicksort(s);
		sortingArray.bucketsort(s);
	}

	/**
	 * Creates an Iterator object to iterate over the table
	 * @return the Iterator
	 */
	public Iterator<Memory> iterator()
	{
		return new HashTableIterator();
	}

	private class HashTableIterator implements Iterator<Memory>
	{
		private int currentBucket;
		private int currentIndex;
		private LinkedList list;
		private int listSize;

		/**
		 * Creates a HashTableIterator object to iterate over the table
		 */
		public HashTableIterator()
		{
			currentBucket = 0;
			currentIndex = 0;
			list = buckets[0];
			listSize = list.size();
		}

		/**
		 * Checks to see if the iterator has a next element 
		 * @return true if there is a next, false otherwise
		 */
		public boolean hasNext() 
		{
			int tempIndex = currentIndex;
			int tempBucket = currentBucket;
			LinkedList tempList = list;
			int tempSize = tempList.size();

			if (tempIndex >= tempSize)
			{
				tempBucket++;
				if (tempBucket >= buckets.length)
					return false;
			}
			return true;
		}

		/**
		 * Gets the next object from the iterator
		 * @return the object
		 */
		public Memory next() 
		{
			list = buckets[currentBucket];
			listSize = list.size();

			if (currentIndex >= listSize) // go to next bucket
			{
				currentIndex = 0;
				currentBucket++;
				list = buckets[currentBucket];
				listSize = list.size();
			}

			return list.getIndex(currentIndex++);                   
		}

		public void remove()
		{
			System.out.println("Not implemented");
		}
	}

}